package pkg

import "fmt"

//1。实现双向链表结构体
type Ring struct {
	Id   int         //节点索引
	Data interface{} //data域
	Prev *Ring       //前驱节点
	Next *Ring       //后驱节点
}

//初始化头节点元素 头节点id初始化为1
func Init(data interface{}) *Ring {
	return &Ring{
		Id:   1,
		Data: data,
	}
}

//2.链表基本判断及末尾元素获取方法
//重置头元素
func (r *Ring) ResetHead(data interface{}) {
	if r.Id == 0 {
		r.Id = 1
	}
	r.Data = data
}

//判断头部是否为空
func (r *Ring) IsHeadEmpty() bool {
	if r.Prev == nil && r.Next == nil {
		return true
	}
	return false
}

//判断是否为空链表
func (r *Ring) IsEmety() bool {
	if r.Data == nil && r.Next == nil && r.Prev == nil && r.Id == 0 {
		return true
	}
	return false
}

//获取末尾元素
func (r *Ring) GetLastNode() *Ring {
	//如果只有一个头元素则直接返回
	listNode := r
	if !r.IsEmety() {
		//如果链表不为空,遍历至最后一个元素
		for {
			if listNode.Next == r { //表示找到了末尾
				break
			}
			listNode = listNode.Next //让当前节点前进
		}
	}
	return listNode
}

//3.对链表添加
//从头节点按顺序插入双向链表节点
func (r *Ring) AddNode(newNode *Ring) {
	//如果只有一个元素则初始化next和prev指针形成双向环形链表
	//如果头节点为空
	if r.IsHeadEmpty() {
		r.Next = newNode
		r.Prev = newNode
		newNode.Prev = r
		newNode.Next = r
		return
	}
	//若环形已形成则按顺序添加节点，把当前节点指向头部
	listNode := r
	//表示是否应进行中间插入
	flag := false //默认表示添加到最后
	for {
		if listNode == r.Prev {
			//已经是最后一个元素表示添加到末尾
			break
		} else if listNode.Next.Id > newNode.Id {
			//当前节点id大于新增节点id
			flag = true
			break
		} else if listNode.Next.Id == newNode.Id {
			//当前节点id等于新增节点id
			fmt.Println("error:id already exists")
			return
		}
		//当前节点继续前进
		listNode = listNode.Next
	}
	if flag { //flag = true
		//在中间添加
		newNode.Next = listNode.Next
		newNode.Prev = listNode
		listNode.Next.Prev = newNode
		listNode.Next = newNode
	} else { //flag = false
		//在末尾添加
		newNode.Prev = listNode
		newNode.Next = listNode.Next
		listNode.Next = newNode
		r.Prev = newNode
	}
}

//4.按照id找到节点
func (r *Ring) findId(id int) (*Ring, bool) {
	if r.IsHeadEmpty() && r.Id == id { //头部为空
		return r, true
	} else if r.IsHeadEmpty() && r.Id != id {
		return &Ring{}, false
	}
	//头部非空 遍历查找
	linkNode := r
	flag := false
	for {
		if linkNode.Id == id {
			flag = true
			break
		}
		if linkNode == r.Prev { //找到最后,表示不存在
			break
		}
		//当前节点继续前进
		linkNode = linkNode.Next
	}
	if !flag { //if flag == flase
		return &Ring{}, false
	}
	return linkNode, true
}

//实现对链表删除指定id的节点
func (r *Ring) DelNodeById(id int) bool {
	if r.IsEmety() {
		fmt.Println("error: NodeList is emety")
		return false
	}
	node, boolvalue := r.findId(id)
	if boolvalue {
		if node == r {
			//处理只有一个头部元素的情况,则把头元素进行id初始化设置并把Data设置为nil
			if r.IsHeadEmpty() {
				r.Next = nil
				r.Prev = nil
				r.Data = nil
				r.Id = 0
				return true
			}
			//如果只有头节点和末尾节点两个元素
			if r.Next.Next == r {
				r.Id = r.Next.Id
				r.Data = r.Next.Data
				r.Next = nil
				r.Prev = nil
				return true
			}
			//如果大于两个节点则移动下一个节点作为头节点
			r.Data = r.Next.Data
			r.Id = r.Next.Id
			r.Next = r.Next.Next
			r.Next.Next.Prev = r
			return true
		}
		//删除的元素是末尾元素
		if node == r.GetLastNode() {
			//如果只有两个元素直接在head节点中断开连接
			if node.Prev == r && node.Next == r {
				r.Next = nil
				r.Prev = nil
				return true
			}
			r.Prev = node.Prev
			node.Prev.Next = r
			return true
		}

		//删除的既不是头也不是尾
		node.Next.Prev = node.Prev
		node.Prev.Next = node.Next
		return true
	} else { //boolvalur == false
		fmt.Println("error: can not find this node!")
	}
	return false
}

//5.根据id修改data
func (r *Ring) modifyData(id int, data interface{}) bool {
	node, boolvalue := r.findId(id)
	if boolvalue {
		node.Data = data
	} else {
		fmt.Println("error:can not find thie id!")
	}
	return boolvalue
}

//遍历整个环形链表
func (r *Ring) FetchAll() {
	if r.IsEmety() {
		fmt.Println("无法遍历空链表")
		return
	}
	if r.IsHeadEmpty() {
		fmt.Println("[", r.Id, r.Data, "next:", r.Next, " perv:", r.Prev, "]")
		return
	}
	currentNode := r
	for {
		fmt.Println("[", currentNode.Id, currentNode.Data, "next:",
			currentNode.Next.Data, " perv:", currentNode.Prev.Data, "]")
		if currentNode == r.Prev {
			break
		}
		currentNode = currentNode.Next
	}
}
